/*
Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
// this file is included in "algorithm.hpp"
#ifndef _SORT_H_VERSION_SSTD__
#define _SORT_H_VERSION_SSTD__

#include "memory.hpp"
#include "functional.hpp"
#define _SSTD_USE_HEAP_
#define _SSTD_USE_SORT_

SSTL_BEGIN
#ifdef _SSTD_USE_HEAP_
// CLASS _heap_ {
template<typename Iterator>
class _heap_
{
public:	
	SSTD_NEST_TYPE_DEFINE(typename iterator_traits<Iterator>::value_type);
	typedef Iterator iterator;
	typedef _iterator_helper_<iterator> _i_helper;
	typedef _memory_helper_<value_type> _helper;
public:
	static  diff_type _parent(diff_type const &suffix)
	{
		return (suffix - 1) >> 1;
	}
	static  diff_type _left(diff_type const &suffix)
	{
		return (suffix << 1) + 1;
	}
	static  diff_type _right(diff_type const &suffix)
	{
		return (suffix + 1) << 1;
	}
	template<typename Less>
	static bool _is_heap(iterator first, diff_type top, diff_type bottom, Less fun)
	{
		if(top >= bottom) return true;
		diff_type sub = _right(top);
		if(sub < bottom)
		{
			if(fun(*(first + top), *(first + sub)) ||
				!_is_heap(first, sub, bottom, fun)) return false;
			--sub;
			if(fun(*(first + top), *(first + sub)) ||
				!_is_heap(first, sub, bottom, fun)) return false;
		}
		else if(sub == bottom)
		{
			--sub;
			if(fun(*(first + top), *(first + sub)) ||
				!_is_heap(first, sub, bottom, fun)) return false;
		}
		return true;
	}
	template<typename Less>
	static void _adjust_up(iterator first, diff_type hole, diff_type top,
		value_type value, Less fun)
	{
		for(diff_type i = hole; i > top; hole = i )
		{
			i = _parent(i);
			if(fun(*(first + i), value)) *(first + hole) = *(first + i);
			else break;
		}
		*(first + hole) = value;
	}
	template<typename Less>
	static void _adjust_down(iterator first, diff_type hole,
		diff_type bottom, value_type value, Less const &fun)
	{
		diff_type top = hole;
		diff_type i = _right(hole);
		for (; i < bottom; i = _right(i))
		{
			if(fun(*(first + i), *(first + (i - 1)))) --i;
			*(first + hole) = *(first + i);
			hole = i;
		}
		if (i-- == bottom)
		{
			*(first + hole) = *(first + i);
			hole = i;
		}
		_adjust_up(first, hole, top, value, fun);
	}
public:
	static  void push_heap(iterator first, iterator last)
	{
		push_heap(first, last, SSTD::less_equal<value_type>());
	}
	template<typename Less>
	static  void push_heap(iterator first, iterator last, Less fun)
	{
		diff_type num = SSTD::distance(first, last);
		if(num <= 1) return;
		_adjust_up(first, num - 1, 0, *--last, fun);
	}
	static  void pop_heap(iterator first, iterator last)
	{
		pop_heap(first, last, SSTD::less_equal<value_type>());
	}
	template<typename Less>
	static  void pop_heap(iterator first, iterator last, Less fun)
	{
		diff_type num = SSTD::distance(first, last);
		if(num <= 1) return;
		value_type value = *--last;
		*last = *first;
		_adjust_down(first, 0, --num, value, fun);
	}
	static void sort_heap(iterator first, iterator last)
	{
		sort_heap(first, last, SSTD::less<value_type>());
	}
	template<typename Less>
	static void sort_heap(iterator first, iterator last, Less fun)
	{
		diff_type num = SSTD::distance(first, last);
		if(num <= 1) return;
		while(--num)
		{
			value_type value = *--last;
			*last = *first;
			_adjust_down(first, 0, num, value, fun);
		}
	}
	static  void make_heap(iterator first, iterator last)
	{
		make_heap(first, last, SSTD::less<value_type>());
	}
	template<typename Less>
	static void make_heap(iterator first, iterator last, Less fun)
	{
		diff_type bottom = SSTD::distance(first, last);
		if(bottom <= 1) return;
		for(diff_type hole = _parent(bottom - 1); hole >= 0; --hole)
		{
			_adjust_down(first, hole, bottom, *(first + hole), fun);
		}
	}
	static bool is_heap(iterator first, iterator last)
	{
		return is_heap(first, last, SSTD::less<value_type>());
	}
	template<typename Less>
	static bool is_heap(iterator first, iterator last, Less fun)
	{
		diff_type bottom = SSTD::distance(first, last);
		return _is_heap(first, 0, bottom, fun);
	}
};
// CLASS _heap_ }
#endif // _SSTD_USE_HEAP_
#ifdef _SSTD_USE_SORT_
static const int _MIN_INSERT_  = 0x20;
static const int _MAX_INSERT_  = 0x80;
static const int _MAX_DEPTH_   = 0x20;

// FUNCTION merge {
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter merge(InIterL first0, InIterL last0, 
					 InIterR first, InIterR last, OutIter result)
{
	return SSTD::merge(first0, last0, first, last, result,
		SSTD::less2<iterator_traits<InIterL>::value_type, 
		iterator_traits<InIterR>::value_type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter merge(InIterL first0, InIterL last0, 
					 InIterR first, InIterR last, 
					 OutIter result, Less less)
{
	if(first0 != last0 && first != last) while(true)
	{
		if(less(*first0, *first))
		{
			*result = *first0, ++first0, ++result;
			if(first0 == last0) break;
		}
		else
		{
			*result = *first, ++first, ++result;
			if(first == last) break;
		}
	}
	result = SSTD::copy(first0, last0, result);
	return SSTD::copy(first, last, result);
}
// FUNCTION merge }
// FUNCTION inplace_merge {
template<typename FwdIter>
inline void inplace_merge(FwdIter first, FwdIter mid, FwdIter last) 
{
	SSTD::inplace_merge(first, mid, last,
		SSTD::less<typename iterator_traits<FwdIter>::value_type>());
}
template<typename FwdIter, typename Less>
inline void inplace_merge(FwdIter first, FwdIter mid, FwdIter last, Less fun) 
{
	if(first == mid || mid == last) return;
	size_t num = SSTD::distance(first, mid);
	size_t num2 = SSTD::distance(mid, last);
	while(num && !fun(*mid, *first)) ++first, --num;
	if(!num) return;
	typedef typename iterator_traits<FwdIter>::value_type value_type;
	typedef SSTD::_memory_helper_<value_type> _helper;
	SSTD::raw_buffer<value_type> buf(num);
	_helper::raw_copy_n(first, num, buf.begin());
	size_t count = 0;
	while(count < num && num2)
	{
		if(fun(*mid, buf[count])) *first = *mid++, --num2;
		else *first = buf[count++];
		++first;
	}
	SSTD::copy(buf.begin() + count, buf.begin() + num, first);
	_helper::destroy_n(buf.begin(), num);
}
template<typename FwdIter, typename Less, typename Value>
inline void _buffered_inplace_merge(FwdIter first, FwdIter mid,
									FwdIter last, size_t num, size_t num2, Less fun, Value *buf) 
{
	if(num == 0 || num2 == 0) return;
	while(num && !fun(*mid, *first)) ++first, --num;
	if(!num) return;
	SSTD::copy_n(first, num, buf);
	size_t count = 0;
	while(count < num && num2)
	{
		if(fun(*mid, buf[count])) *first = *mid++, --num2;
		else *first = buf[count++];
		++first;
	}
	SSTD::copy(buf + count, buf + num, first);
}
// FUNCTION inplace_merge }
// FUNCTION insert_sort {
template<typename RanIter>
inline void insert_sort(RanIter first, RanIter last)
{
	SSTD::insert_sort(first, last,
		SSTD::less<SSTD::iterator_traits<RanIter>::value_type>());
}
template<typename BidIter, typename Less>
inline void insert_sort(BidIter first, BidIter last, Less &fun)
{
	typedef typename SSTD::iterator_traits<BidIter>::value_type value_type;
	if (first == last) return;
	for (BidIter next = first; ++next != last; )
	{
		BidIter hole = next;
		value_type value = *next;
		if(fun(value, *first))
		{
			SSTD::copy_backward(first, next, ++hole);
			*first = value;
		}
		else if(fun(value, *--hole))
		{
			BidIter temp = hole; *next = *hole;
			while(fun(value, *--hole))
				*temp = *hole, temp = hole;
			*temp = value;
		}
	}
}
// FUNCTION insert_sort }
// FUNCTION stable_sort {
template<typename BidIter>
inline void stable_sort(BidIter first, BidIter last)
{
	SSTD::stable_sort(first, last,
		SSTD::less<iterator_traits<BidIter>::value_type>());
}
template<typename BidIter, typename Less>
inline void stable_sort(BidIter first, BidIter last, Less fun)
{
	typedef typename SSTD::iterator_traits<BidIter>::value_type value_type;
	diff_t num = SSTD::distance(first, last);
	if(num < 2) return;
	if(num > _MAX_INSERT_)
	{
		SSTD::buffer<value_type> buf(num/2);
		SSTD::_bin_sort(first, last, num, fun, buf.begin());
	}
	else SSTD::insert_sort(first, last);
}
template<typename BidIter, typename Less, typename Value>
inline void _bin_sort(BidIter first, BidIter last, size_t num,
					  Less &fun, Value *buf)
{
	if(num < 2) return;
	if(num > _MAX_INSERT_)
	{
		BidIter mid = SSTD::_iterator_helper_<BidIter>::forward(first, num / 2);
		SSTD::_bin_sort(first, mid, num/2, fun, buf);
		SSTD::_bin_sort(mid, last, num - num/2, fun, buf);
		SSTD::_buffered_inplace_merge(first, mid, last, 
			num/2, num - num/2, fun, buf);
	}
	else SSTD::insert_sort(first, last, fun);
}
// FUNCTION stable_sort }
// FUNCTION sort {
template<typename RanIter>
inline void sort(RanIter first, RanIter last)
{
	SSTD::sort(first, last, SSTD::less<SSTD::iterator_traits<RanIter>::value_type>());
}
template<typename RanIter, typename Less>
inline void sort(RanIter first, RanIter last, Less fun)
{
	SSTD::_sort(first, last, fun, 0);
}
template<typename RanIter, typename Less>
inline void _sort(RanIter first, RanIter last, Less &fun, size_t depth)
{
	diff_t num = SSTD::distance(first, last);
	if(num <= 1) return;
	if(is_sorted(first, last, fun)) return;
	if(num < _MIN_INSERT_) SSTD::insert_sort(first, last, fun);
	else if(depth > _MAX_DEPTH_)
	{
		if(num < _MAX_INSERT_) SSTD::insert_sort(first, last, fun);
		else SSTD::heap_sort(first, last, fun);
	}
	else
	{
		RanIter mid = first + num / 2;
		SSTD::_sort3(first, mid, last, num, fun);
		mid = SSTD::partition(first, last, SSTD::bind2nd(fun, *mid));
		if(mid == first || mid == last)
		{
			if(num < _MAX_INSERT_) SSTD::insert_sort(first, last, fun);
			else
			{
				SSTD::pair<RanIter, RanIter> mid_pair = 
					SSTD::_middle_partition(first, last, fun);
				SSTD::_sort(first, mid_pair.first, fun, ++depth);
				SSTD::_sort(mid_pair.second, last, fun, depth);
			}
		}
		else
		{
			SSTD::_sort(first, mid, fun, ++depth);
			SSTD::_sort(mid, last, fun, depth);
		}
	}
}
template<typename RanIter, typename Less>
inline SSTD::pair<RanIter, RanIter> _middle_partition(RanIter first, RanIter last,
													 Less &fun)
{	// from VS STL : _Unguarded_partition
	diff_t num = SSTD::distance(first, last);
	if(num < 2) return SSTD::pair<RanIter, RanIter>(first, last);
	RanIter mid = first + num / 2;
	SSTD::_sort3(first, mid, last, num, fun);
	RanIter prev = mid;
	RanIter next = mid + 1;	
	while (first < prev 
		&& !fun(*(prev - 1), *prev) && !fun(*prev, *(prev - 1))) --prev;
	while (next < last && !fun(*next, *prev) && !fun(*prev, *next)) ++next;
	RanIter pprev = prev;
	RanIter nnext = next;
	while(true)
	{
		while (nnext < last)
		{
			if(fun(*nnext, *prev)) break;
			if(fun(*prev, *nnext)) ++nnext;
			else SSTD::iter_swap(nnext++, next++);
		}
		while (first < pprev)
		{
			if(fun(*prev, *(pprev - 1))) break;
			if(fun(*(pprev - 1), *prev)) --pprev;
			else SSTD::iter_swap(--pprev, --prev);
		}
		if(nnext == last && pprev == first)
			return SSTD::pair<RanIter, RanIter>(prev, next);
		else if(nnext == last)
		{
			--pprev, --prev, --next;
			if(pprev != prev) SSTD::iter_swap(prev, pprev);
			SSTD::iter_swap(prev, next);
		}
		else if(pprev == first)
		{
			if(nnext != next) SSTD::iter_swap(nnext, next);
			SSTD::iter_swap(next, prev);
			++nnext, ++next, ++prev;
		}
		else SSTD::iter_swap(nnext++, --pprev);
	}
	return SSTD::pair<RanIter, RanIter>(prev, next);
}
template<typename RanIter, typename Less>
inline void _sort3(RanIter first, RanIter mid, RanIter last, size_t num, Less &fun)
{	// sort 3 elements.	
	if(num < 3) return;
	if(fun(*mid, *first)) SSTD::iter_swap(first, mid);
	if(fun(*--last, *mid))
	{
		SSTD::iter_swap(last, mid);
		if(fun(*mid, *first)) SSTD::iter_swap(first, mid);
	}
}
// FUNCTION sort }
// FUNCTION nth_element {
template<typename RanIter>
inline void nth_element(RanIter first, RanIter mid, RanIter last)
{
	SSTD::nth_element(first, mid, last, 
		SSTD::less<iterator_traits<RanIter>::value_type>());
}
template<typename RanIter, typename Less>
inline void nth_element(RanIter first, RanIter mid, RanIter last, Less fun)
{
	ASSERT_REPAIR(!(first > mid) && !(last < mid), return);
	while(last - first > _MIN_INSERT_)
	{
		SSTD::pair<RanIter, RanIter> mid_pair = 
			SSTD::_middle_partition(first, last, fun);
		if(mid < mid_pair.first) last = mid_pair.first;
		else if(mid < mid_pair.second) return;
		else first = mid_pair.second;
	}
	SSTD::insert_sort(first, last, fun);
}
// FUNCTION nth_element }
// FUNCTION partition, stable_partition {
template<typename BidIter, typename Bool>
inline BidIter partition(BidIter first, BidIter last, Bool fun)
{
	for(; first != last; ++first)
	{
		while(fun(*first) && ++first != last);
		if(first == last) break;
		while(first != --last && !fun(*last));
		if(first == last) break;
		SSTD::iter_swap(first, last);
	}
	return first;
}
template<typename BidIter, typename Bool>
inline BidIter stable_partition(BidIter first, BidIter last, Bool fun)
{
	while(first != last && fun(*first)) ++first;
	if(first == last) return first;
	while(first != --last && !fun(*last));
	if(first == last) return first;
	// redo partition.
	size_t num = SSTD::distance(first, ++last);
	typedef typename iterator_traits<BidIter>::value_type value_type;
	SSTD::raw_buffer<value_type> buf(num);
	size_t count = 0;
	for(BidIter next = first; next != last; ++next)
	{
		if(fun(*next)) *first = *next, ++first;
		else SSTD::construct(buf.begin() + count++, *next);
	}
	SSTD::copy(buf.begin(), buf.begin() + count, first);
	SSTD::destroy(buf.begin(), buf.begin() + count);
	return first;
}
// FUNCTION partition, stable_partition }
// FUNCTION xxx_heap {
template<typename RanIter, typename Less>
inline void make_heap(RanIter first, RanIter last, Less fun)
{
	_heap_<RanIter>::make_heap(first, last, fun);
}
template<typename RanIter, typename Less>
inline void sort_heap(RanIter first, RanIter last, Less fun)
{
	_heap_<RanIter>::sort_heap(first, last, fun);
}
template<typename RanIter, typename Less>
inline void push_heap(RanIter first, RanIter last, Less fun)
{
	_heap_<RanIter>::push_heap(first, last, fun);
}
template<typename RanIter, typename Less>
inline void pop_heap(RanIter first, RanIter last, Less fun)
{
	_heap_<RanIter>::pop_heap(first, last, fun);
}
template<typename RanIter, typename Less>
inline bool is_heap(RanIter first, RanIter last, Less fun)
{
	return _heap_<RanIter>::is_heap(first, last, fun);
}
template<typename RanIter>
inline void make_heap(RanIter first, RanIter last)
{
	_heap_<RanIter>::make_heap(first, last);
}
template<typename RanIter>
inline void sort_heap(RanIter first, RanIter last)
{
	_heap_<RanIter>::sort_heap(first, last);
}
template<typename RanIter>
inline void push_heap(RanIter first, RanIter last)
{
	_heap_<RanIter>::push_heap(first, last);
}
template<typename RanIter>
inline void pop_heap(RanIter first, RanIter last)
{
	_heap_<RanIter>::pop_heap(first, last);
}
template<typename RanIter>
inline bool is_heap(RanIter first, RanIter last)
{
	return _heap_<RanIter>::is_heap(first, last);
}
// FUNCTION xxx_heap }
// FUNCTION heap_sort (x) {
template<typename RanIter>
inline void heap_sort(RanIter first, RanIter last)
{
	SSTD::make_heap(first, last);
	SSTD::sort_heap(first, last);
}
template<typename RanIter, typename Less>
inline void heap_sort(RanIter first, RanIter last, Less fun)
{
	SSTD::make_heap(first, last, fun);
	SSTD::sort_heap(first, last, fun);
}
// FUNCTION heap_sort (x) }
// FUNCTION partial_sort, partial_sort_copy {
template<typename RanIter>
inline void partial_sort(RanIter first, RanIter mid, RanIter last)
{
	SSTD::partial_sort(first, mid, last,
		SSTD::less<iterator_traits<RanIter>::value_type>());
}
template<typename RanIter, typename Less>
inline void partial_sort(RanIter first, RanIter mid, RanIter last, Less fun)
{
	typedef SSTD::iterator_traits<RanIter>::value_type value_type;
	diff_t bottom = SSTD::distance(first, mid);
	if(bottom <= 0) return;
	SSTD::make_heap(first, mid);
	for(RanIter temp = mid; temp < last; ++temp)
	{
		if(fun(*temp, *first))
		{	// remove top and insert temp.
			value_type value = *temp;
			*temp = *first;
			SSTD::_heap_<RanIter>::_adjust_down(first, 0, bottom, value, fun);
		}
	}
	SSTD::sort_heap(first, mid);
}
template<typename RanIterSrc, typename RanIterDest>
inline RanIterDest partial_sort_copy(RanIterSrc first0, RanIterSrc last0,
									 RanIterDest first, RanIterDest last)
{
	return SSTD::partial_sort_copy(first0, last0, first, last,
		SSTD::less2<iterator_traits<RanIterSrc>::value_type,
		iterator_traits<RanIterDest>::value_type>());
}
template<typename RanIterSrc, typename RanIterDest, typename Less>
inline RanIterDest partial_sort_copy(RanIterSrc first0, RanIterSrc last0,
									 RanIterDest first, RanIterDest last, Less fun)
{
	RanIterDest mid = first;
	for(; mid != last && first0 != last0; ++first0, ++mid)	*mid = *first0;
	diff_t bottom = SSTD::distance(first, mid);
	if(bottom <= 0) return mid;
	SSTD::make_heap(first, mid);
	for(; first0 != last0; ++first0)
	{
		if(fun(*first0, *first))
		{	// remove top and insert temp.
			SSTD::_heap_<RanIterDest>::_adjust_down(first, 0, bottom, *first0, fun);
		}
	}
	SSTD::sort_heap(first, mid);
	return mid;
}
// FUNCTION partial_sort, partial_sort_copy }
#endif // _SSTD_USE_SORT_
SSTL_END
#endif // _SORT_H_VERSION_SSTD__
